package com.javaDemo.ti;

/**
 * @ClassName: GongGongzuxian
 * @Auther: csy
 * @Date: 2022/3/30 16:13
 * @Description: 二叉树的最近公共祖先问题
 *               给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
 *               最近公共祖先的定义：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，
 *               满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。
 */
public class GongGongzuxian {

    /**
     * 二叉树节点定义
     */
    public static class TreeNode {
        // 节点值
        int val;
        // 左子节点
        TreeNode left;
        // 右子节点
        TreeNode right;

        /**
         * 构造函数
         * 
         * @param val 节点值
         */
        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return "TreeNode{val=" + val + "}";
        }
    }

    /**
     * 主方法，用于测试最近公共祖先算法
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 创建测试用例：构建一个简单的二叉树
        // 2
        // /\
        // 3 null
        // /\
        // null 6
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(3);
        // root.left.left = new TreeNode(5); // 注释掉的节点，可以取消注释进行更复杂的测试
        root.left.right = new TreeNode(6);

        // 查找节点3和节点6的最近公共祖先
        TreeNode p = root.left; // 节点3
        TreeNode q = root.left.right; // 节点6
        TreeNode result = lowestCommonAncestor(root, p, q);

        // 输出结果
        System.out.println("节点" + p.val + "和节点" + q.val + "的最近公共祖先是：" + result);
    }

    /**
     * 查找二叉树中两个节点的最近公共祖先
     * 算法思想：后序遍历（左右根）+ 递归
     * 
     * @param root 二叉树根节点
     * @param p    第一个目标节点
     * @param q    第二个目标节点
     * @return 最近公共祖先节点
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 基本情况：如果当前节点为空，或者当前节点就是p或q，则返回当前节点
        if (root == null || root == p || root == q) {
            return root;
        }

        // 后序遍历：先递归搜索左右子树
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q); // 在左子树中查找
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q); // 在右子树中查找

        // 根据左右子树的搜索结果，确定最近公共祖先
        if (leftResult == null && rightResult == null) {
            // 情况1：左右子树都没找到p和q，返回null表示当前子树不包含p和q
            return null;
        } else if (leftResult == null) {
            // 情况2：左子树没找到，右子树找到了至少一个节点，返回右子树的结果
            return rightResult;
        } else if (rightResult == null) {
            // 情况3：右子树没找到，左子树找到了至少一个节点，返回左子树的结果
            return leftResult;
        } else {
            // 情况4：左右子树各找到一个节点，说明当前root就是最近公共祖先
            return root;
        }
    }
}
